Technical Field
This disclosure relates to wireless networks and to timing synchronization in such networks.
Description of Related Art
Timing, defined here as a process of aligning time origins/references (offsets) and rates (skews) of two physically separate time keeping devices, is a fundamental task in wireless networks. One of its components, namely frequency (clock rate) synchronization, can be achieved by devices using phase-locked loops to adjust their local oscillator frequency to a master clock (base station, GPS satellite, or another device within an ad-hoc network). However, alignment of time offsets (including propagation delays) can be more involved. It can be achieved by many different techniques, motivated by the fact that different degrees of precision are required for different applications.
Timing a network of wired/wireless nodes is not a new problem. For example, computers connected to the Internet, and cellular phones connected to a base station are examples of networked devices that attempt to keep a common time reference (also W. Lindsey, F. Ghazvinian, W. Hagmann, and K. Dessouky, “Network synchronization,” Proceedings of the IEEE, vol. 73, no. 10, pp. 1445-1467, October 1985; P. Ranganathan and K. Nygrad, “Time synchronization in wireless sensor networks: A survey,” Int. Journal of UbiComp, vol. 1, no. 2, pp. 92-102, July 2010, and references therein). However, such approaches may have limitations in terms of precision or network size. Small networks can broadcast a high-precision reference clock to all nodes in the network (as is done, e.g., in GPS, or the transmission of a clock to cellular users). Many communication systems establish synchronization only within the accuracy of a symbol duration and/or the cyclic prefix duration, which often obviates the need for compensating for the runtime of signals, A. F. Molisch, “Wireless communications,” second ed., Chichester, West Sussex, England: John Wiley & Sons Ltd., 2011. Narrowband coherent superposition can be achieved by phase synchronization, A. F. Molisch, “Wireless communications,” second ed., Chichester, West Sussex, England: John Wiley & Sons Ltd., 2011, which, however, may contain an ambiguity in timing. However, when the expected precision of timing is much smaller than the propagation delays in the system (potentially even smaller than the inverse carrier frequency) and the network is large, the problem may require new solutions.
Precise timing of large, randomly deployed wireless networks can be challenging. Each node's timer may be derived from an independent oscillator, which may be affected by long/short term frequency drifts and jitter, J. Esterline, “Oscillator phase noise: theory vs practicality,” Greenray industries, inc. report, April 2008. For example, if a timer is left uncorrected, its timing error growth can be modeled by a one dimensional random walk (sometimes modeled as a Wiener process). Even if two oscillators are perfectly matched in frequency and phase at the time instance t1*, the random frequency errors may lead to an error at time t2* with a variance ∝t2*−t1* (t* denotes absolute time) (The actual oscillator characteristics may be more complex than this description.) Mitigating the effect of this clock error, which may be critical for essential timing, may require very fast re-timing of the clocks.
A second issue may be the limitation on the precision of timing information exchange in finite-bandwidth channels with noise. The process of timing information exchange can be defined as the task of conveying information about a ‘point’ in time. Also, a band limited energy limited signal can, in principle, contain multiple ‘points’ which are similar. In addition, wireless channels can create ambiguity by generating multiple copies of the ‘point’, which can make the (time of arrival) TOA estimation error prone. With finite bandwidth, TOA estimation error—a measure of timing information may be directly effected by the transmission bandwidth (BW), Y. Shen and M. Z. Win, “Fundamental Limits of Wideband Localization Part I: A General Framework,” Information Theory, IEEE Transactions on, vol. 56, no. 10, October 2010, pp. 4956-4980. If a node's TOA estimation error variance is σTOA2, it may not achieve timing accuracy any better than σTOA2, (unless some diversity is used). Due to the ease of achieving high TOA estimation accuracy, wide band signaling may be desirable for time transfer, C.-C. Chui and R. Scholtz, “Time transfer in impulse radio networks,” Communications, IEEE Transactions on, vol. 57, no. 9, pp. 2771-2781, September 2009; A.-S. Hu and S. Servetto, “On the scalability of cooperative time synchronization in pulse-connected networks,” Information Theory, IEEE Transactions on, vol. 52, no. 6, pp. 2725-2748, June 2006; however a very large BW may not be mandatory for some applications, this is discussed further below.
Higher BW may help TOA estimation in two ways. It may increase the slew rate of the signal, thus increasing the timing information content of the ‘point’. It may increase the resolvability among multipath components and among points on the same signal.
The above issues may affect the timing between any pair of nodes. A significant further complication may occur in large networks with random deployment of nodes. Due to the size of the network, direct transmission of timing pulses from a “master” to all other nodes in the network may not be possible. Thus, the timing information may have to propagate through the network, possibly aggregating errors. Due to random deployment, network topology may be unknown, creating a need for a solution that is scalable and be robust to changes. A number of distributed algorithms were proposed for network timing. A. Giridhar and P. Kumar, “Distributed clock synchronization over wireless networks: Algorithms and analysis,” Decision and Control, 2006 45th IEEE Conference on, December 2006, pp. 4915-4920, describes the mathematical foundation for an averaging based distributed consensus algorithm for timing, though neither a fully functional algorithm, nor fast re-timing was within the scope of this reference. A packet based distributed timing algorithm proposed in B. J. Choi, H. Liang, X. Shen, and W. Zhuang, “Dcs: Distributed asynchronous clock synchronization in delay tolerant networks,” Parallel and Distributed Systems, IEEE Transactions on, vol. 23, no. 3, pp. 491-504, March 2012, uses an elegant clock table structure to acquire the timing information from nodes that are multiple hops away. However, due to the assumption of negligible TOA errors, and the sharing of clock tables and packet based time transfer, it may not be suitable for the aforementioned target applications. Other examples of packet based time transfer algorithms are L. Schenato and G. Gamba, “A distributed consensus protocol for clock synchronization in wireless sensor network,” in Decision and Control, 2007 46th IEEE Conference on, December 2007, pp. 2289-2294 and M. Leng and Y.-C. Wu, “Distributed clock synchronization for wireless sensor networks using belief propagation,” Signal Processing, IEEE Transactions on, vol. 59, no. 11, pp. 5404-5414, November 2011, however fast re-timing was not within their scope; furthermore L. Schenato and G. Gamba, “A distributed consensus protocol for clock synchronization in wireless sensor network,” in Decision and Control, 2007 46th IEEE Conference on, December 2007, pp. 2289-2294 neglects propagation delay differences, and rate adjustment is not dealt with in M. Leng and Y.-C. Wu, “Distributed clock synchronization for wireless sensor networks using belief propagation,” Signal Processing, IEEE Transactions on, vol. 59, no. 11, pp. 5404-5414, November 2011.